package com.javaDemo.ti;

import java.util.*;

/**
 * 数组和字符串类算法题详解
 * 
 * @author csy
 * @description 面试中常见的数组和字符串类算法题的详细解析
 */
public class ArrayAndStringExamples {

    /**
     * 【数组类】三数之和
     * 
     * 问题描述：
     * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
     * 使得 a + b + c = 0？找出所有满足条件且不重复的三元组。
     * 
     * 解题思路详解：
     * 1. 为什么要先排序？
     * - 排序后可以使用双指针降低时间复杂度
     * - 排序后可以方便地跳过重复元素
     * 
     * 2. 详细步骤解析：
     * a) 数组排序
     * - 为什么：便于使用双指针和去重
     * - 如何：使用Arrays.sort()
     * 
     * b) 固定第一个数
     * - 为什么：将三数之和转化为两数之和
     * - 如何：遍历数组，注意去重
     * 
     * c) 双指针查找另外两个数
     * - 为什么：O(n)时间内找到剩余两个数
     * - 如何：左右指针向中间移动
     * 
     * 3. 去重策略详解：
     * a) 第一个数的去重
     * - 当前数字和前一个数字相同时跳过
     * b) 左指针去重
     * - 找到解后，跳过相同的左指针数字
     * c) 右指针去重
     * - 找到解后，跳过相同的右指针数字
     * 
     * 4. 优化策略：
     * a) 特殊情况判断
     * - 数组为null或长度小于3时直接返回
     * - 第一个数大于0时直接结束
     * b) 指针移动优化
     * - 和大于0时右指针左移
     * - 和小于0时左指针右移
     * 
     * 5. 举例详解：
     * 输入：nums = [-1, 0, 1, 2, -1, -4]
     * 排序后：[-4, -1, -1, 0, 1, 2]
     * 
     * 第一轮：选择-4
     * - left=1, right=5: -4 + (-1) + 2 = -3 < 0, left++
     * - left=2, right=5: -4 + (-1) + 2 = -3 < 0, left++
     * ...
     * 
     * 第二轮：选择-1
     * - left=2, right=5: -1 + (-1) + 2 = 0 √
     * - 记录[-1,-1,2]，跳过重复的-1
     * ...
     * 
     * 时间复杂度：O(n²)
     * 空间复杂度：O(1)（不考虑存储结果的空间）
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 3)
            return result;

        // 1. 排序
        Arrays.sort(nums);

        // 2. 固定第一个数，然后使用双指针找其他两个数
        for (int i = 0; i < nums.length - 2; i++) {
            // 第一个数大于0，后面的数都大于0，不可能有解
            if (nums[i] > 0)
                break;

            // 去重：跳过重复的第一个数
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    // 找到一组解
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 去重：跳过重复的左指针数字
                    while (left < right && nums[left] == nums[left + 1])
                        left++;
                    // 去重：跳过重复的右指针数字
                    while (left < right && nums[right] == nums[right - 1])
                        right--;

                    left++;
                    right--;
                } else if (sum < 0) {
                    // 和小于0，左指针右移
                    left++;
                } else {
                    // 和大于0，右指针左移
                    right--;
                }
            }
        }

        return result;
    }

    /**
     * 【数组类】合并区间
     * 
     * 问题描述：
     * 给出一个区间的集合，请合并所有重叠的区间。
     * 
     * 解题思路详解：
     * 1. 为什么要先排序？
     * - 排序后可以保证相邻的区间是最可能重叠的
     * - 只需要比较当前区间和结果集中最后一个区间
     * 
     * 2. 详细步骤解析：
     * a) 特殊情况处理
     * - 为什么：处理边界情况
     * - 如何：检查数组是否为空
     * 
     * b) 区间排序
     * - 为什么：使重叠区间相邻
     * - 如何：按照区间起点排序
     * 
     * c) 合并过程
     * - 为什么：需要逐个比较和合并
     * - 如何：比较当前区间和结果集最后一个区间
     * 
     * 3. 合并策略详解：
     * a) 判断是否需要合并
     * - 当前区间的起点 <= 前一个区间的终点
     * b) 合并操作
     * - 更新前一个区间的终点为两个区间终点的最大值
     * 
     * 4. 举例详解：
     * 输入：[[1,3],[2,6],[8,10],[15,18]]
     * 
     * 排序后（已经有序）：
     * 第一轮：添加[1,3]
     * 第二轮：
     * - 当前区间[2,6]
     * - 2 <= 3，需要合并
     * - 更新为[1,6]
     * 
     * 第三轮：
     * - 当前区间[8,10]
     * - 8 > 6，不需要合并
     * - 添加[8,10]
     * ...
     * 
     * 时间复杂度：O(nlogn)，主要是排序的时间
     * 空间复杂度：O(n)，需要存储结果
     */
    public static int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }

        // 1. 按区间起点排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> result = new ArrayList<>();
        result.add(intervals[0]);

        // 2. 遍历并合并区间
        for (int i = 1; i < intervals.length; i++) {
            int[] current = intervals[i];
            int[] last = result.get(result.size() - 1);

            // 判断是否需要合并
            if (current[0] <= last[1]) {
                // 合并区间，更新结果集中最后一个区间的终点
                last[1] = Math.max(last[1], current[1]);
            } else {
                // 不需要合并，添加新区间
                result.add(current);
            }
        }

        return result.toArray(new int[result.size()][]);
    }

    /**
     * 【字符串类】字符串解码
     * 
     * 问题描述：
     * 给定一个经过编码的字符串，返回它解码后的字符串。
     * 编码规则是：k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。
     * 
     * 解题思路详解：
     * 1. 为什么使用栈？
     * - 需要处理嵌套的括号结构
     * - 栈可以保存之前的状态
     * 
     * 2. 详细步骤解析：
     * a) 初始化数据结构
     * - 数字栈：存储重复次数
     * - 字符串栈：存储待拼接的字符串
     * 
     * b) 遍历字符串
     * - 数字：累积多位数字
     * - 左括号：保存当前状态
     * - 字母：累积当前字符串
     * - 右括号：处理栈顶元素
     * 
     * 3. 处理策略详解：
     * a) 遇到数字
     * - 为什么：可能是多位数字
     * - 如何：累积数字值
     * 
     * b) 遇到左括号
     * - 为什么：需要保存当前状态
     * - 如何：将当前数字和字符串入栈
     * 
     * c) 遇到右括号
     * - 为什么：需要处理重复逻辑
     * - 如何：弹出栈顶元素并处理重复
     * 
     * 4. 举例详解：
     * 输入："3[a2[c]]"
     * 
     * 处理过程：
     * 1) 遇到3：num = 3
     * 2) 遇到[：
     * - 保存3和""
     * - 重置状态
     * 3) 遇到a：cur = "a"
     * 4) 遇到2：num = 2
     * 5) 遇到[：
     * - 保存2和"a"
     * - 重置状态
     * ...
     * 
     * 时间复杂度：O(n)，其中n是字符串长度
     * 空间复杂度：O(n)，栈的空间
     */
    public static String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> stringStack = new Stack<>();
        StringBuilder currentString = new StringBuilder();
        int count = 0;

        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                // 处理数字
                count = count * 10 + (ch - '0');
            } else if (ch == '[') {
                // 遇到左括号，保存当前状态
                countStack.push(count);
                stringStack.push(currentString);
                // 重置状态
                count = 0;
                currentString = new StringBuilder();
            } else if (ch == ']') {
                // 遇到右括号，处理重复逻辑
                StringBuilder temp = currentString;
                currentString = stringStack.pop();
                int repeatTimes = countStack.pop();

                // 重复字符串
                for (int i = 0; i < repeatTimes; i++) {
                    currentString.append(temp);
                }
            } else {
                // 处理字母
                currentString.append(ch);
            }
        }

        return currentString.toString();
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试三数之和
        System.out.println("=== 三数之和测试 ===");
        int[] nums1 = { -1, 0, 1, 2, -1, -4 };
        List<List<Integer>> threeSum = threeSum(nums1);
        System.out.println("输入数组：" + Arrays.toString(nums1));
        System.out.println("结果：" + threeSum + "\n");

        // 测试合并区间
        System.out.println("=== 合并区间测试 ===");
        int[][] intervals = { { 1, 3 }, { 2, 6 }, { 8, 10 }, { 15, 18 } };
        int[][] merged = merge(intervals);
        System.out.println("输入区间：" + Arrays.deepToString(intervals));
        System.out.println("合并结果：" + Arrays.deepToString(merged) + "\n");

        // 测试字符串解码
        System.out.println("=== 字符串解码测试 ===");
        String s1 = "3[a2[c]]";
        System.out.println("输入字符串：" + s1);
        System.out.println("解码结果：" + decodeString(s1));
    }
}